package com.datastructure.test.doubletoken.combineofInterval;

import java.util.ArrayList;
import java.util.Stack;

public class CombineOfInterval {
    Stack<Interval> intervalStack = new Stack<>();
    Interval temp;
    ArrayList<Interval> result;

    public static void main(String[] args) {
        ArrayList<Interval> data = new ArrayList<>();
        data.add(new Interval(10,30));
        data.add(new Interval(20,60));
        data.add(new Interval(80,100));
        data.add(new Interval(150,180));
        CombineOfInterval combineOfInterval = new CombineOfInterval();
        combineOfInterval.merge(data);
        System.out.println(data);
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        sortIntervals(intervals);

        return getInternals(intervals);
    }

    public ArrayList<Interval> getInternals(ArrayList<Interval> intervals){
        if(intervals.size()==0||intervals.size()==1){
            return intervals;
        }
        for (int i = 0; i < intervals.size(); i++) {
            if(i==0){
                intervalStack.add(intervals.get(i));
            } else {
                Interval pop = intervalStack.pop();
                if(pop.end<intervals.get(i).start){
                    intervalStack.add(pop);
                    intervalStack.add(intervals.get(i));
                } else if(pop.end>intervals.get(i).start&&pop.end>=intervals.get(i).end){
                    intervalStack.add(pop);
                } else if((pop.end==intervals.get(i).start)||(pop.end>intervals.get(i).start&&pop.end<intervals.get(i).end)){
                    temp = new Interval(pop.start, intervals.get(i).end);
                    intervalStack.add(temp);
                }
            }
        }
       result = new ArrayList<>();
        result.addAll(intervalStack);
        return result;
    }

    public void sortIntervals(ArrayList<Interval> intervals){
        for(int i = 1;i<intervals.size();i++){
            Interval value = intervals.get(i);
            int index = i-1;
            while (index>=0&&value.start<intervals.get(index).start){
                intervals.set(index+1,intervals.get(index));
                index--;
            }
            if(index+1!=i){
                intervals.set(index+1,value);
            }
        }
    }

}
class Interval {
   int start;
   int end;
   Interval() { start = 0; end = 0; }
   Interval(int s, int e) { start = s; end = e; }
}

